package elka.gis.postman.helper.impl;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.Stack;

import elka.gis.postman.bean.Edge;
import elka.gis.postman.bean.Graph;
import elka.gis.postman.bean.Vertex;
import elka.gis.postman.helper.GraphConnectivityChecker;

/**
 * Klasa umozliwiajaca sprawdzanie spojnosci grafu
 * @author Wojtek
 *
 */
public class GraphConnectivityCheckerImpl implements GraphConnectivityChecker {

	public boolean isConnectivity(Graph graph) {
		Set<Vertex> visited = new HashSet<Vertex>();
		Stack<Vertex> stack = new Stack<Vertex>();
		stack.push(graph.getVertices().get(0));
		while(!stack.isEmpty()){
			Vertex actualVertex = stack.pop();
			visited.add(actualVertex);
			List<Vertex> succesors = getSuccesors(actualVertex);
			for (Vertex v :succesors){
				if(!visited.contains(v)){
					stack.push(v);
				}
			}
			
			
			
		}
		
		
		return graph.getVertices().size() == visited.size();
	}
	
	private List<Vertex> getSuccesors(Vertex v){
		List<Vertex> result = new ArrayList<Vertex>();
		
		for(Edge e: v.getEdges()){
			result.add(chooseTargetVertex(e, v));
		}
		return result;
		
	}
	
	private Vertex chooseTargetVertex(Edge e,Vertex startVertex){
		if(e.getStartPoint().equals(startVertex)){
			return e.getEndPoint();
		}else{
			return e.getStartPoint();
		}
	}
	
}
